/**
 * 
 */
package com.module.bp.bus.graph;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Stack;

public final class SimpleGraph {
	/** flag for debugging. */
	private boolean						debugOn	= false;
	/** the total number of edges in the graph. */
	private int							edges;
	/** the total number of vertices (nodes) in the graph. */
	private int							vertices;
	private ArrayList<WeightedEdge>[]	weightedEdges;
	private ArrayList<WeightedEdge>[]	roadEdges;
	/**
	 * Create an empty graph with V vertices.
	 * @throws java.lang.IllegalArgumentException if V < 0
	 */
	public SimpleGraph(final int numVertices) {
		if (numVertices < 0) {
			throw new IllegalArgumentException(
					"Number of vertices must be nonnegative");
		}
		vertices = numVertices;
		edges = 0;
		weightedEdges = new ArrayList[numVertices];
		for (int v = 0; v < numVertices; v++) {
			weightedEdges[v] = new ArrayList<WeightedEdge>();
		}
		roadEdges = new ArrayList[numVertices];
		for (int v = 0; v < numVertices; v++) {
			roadEdges[v] = new ArrayList<WeightedEdge>();
		}
	}
	/**
	 * Copy constructor.
	 */
	public SimpleGraph(final SimpleGraph G) {
		this(G.getNumVertices());
		edges = G.getNumEdges();
		for (int v = 0; v < G.getNumVertices(); v++) {
			// reverse so that adjacency list is in same order as original
			Stack<WeightedEdge> reverse2 = new Stack<WeightedEdge>();
			for (WeightedEdge w : G.weightedEdges[v]) {
				reverse2.push(w);
			}
			for (WeightedEdge w : reverse2) {
				weightedEdges[v].add(w);
			}
		}
	}
	public void addVertex() {
		vertices++;
		ArrayList<WeightedEdge>[] dest2 = new ArrayList[vertices];
		System.arraycopy(weightedEdges, 0, dest2, 0, weightedEdges.length);
		dest2[vertices - 1] = new ArrayList<WeightedEdge>();
		weightedEdges = dest2;
		dest2 = null;
	}
	/**
	 * Adds a weighted edge to the graph.
	 * @param from the source vertex
	 * @param to the vertex the edge connects to
	 * @param weight the edge's weight
	 * @param directed if true, the edge is directed and is only added as an 
	 * edge from the original vertext to its destination; otherwise a parallel 
	 * edge is added to the destination vertex
	 */
	public void addRoadEdge(final int from, final int to,
			final float weight, final boolean directed) {
		addRoadEdge(new WeightedEdge(from, to, weight), directed);
	}
	/**
	 * Adds a weighted edge to the graph.
	 * @param from the source vertex
	 * @param to the vertex the edge connects to
	 * @param weight the edge's weight
	 * @param directed if true, the edge is directed and is only added as an 
	 * edge from the original vertext to its destination; otherwise a parallel 
	 * edge is added to the destination vertex
	 */
	public void addWeightedEdge(final int from, final int to,
			final float weight, final boolean directed) {
		addWeightedEdge(new WeightedEdge(from, to, weight), directed);
	}
	/**
	 * Adds a weighted edge to the graph.
	 * @param e the edge
	 * @param directed if true, the edge is directed and is only added as an 
	 * edge from the original vertext to its destination; otherwise a parallel 
	 * edge is added to the destination vertex
	 */
	public void addWeightedEdge(final WeightedEdge e, final boolean directed) {
		if (e.getFrom() < 0 || e.getFrom() >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		if (e.getTo() < 0 || e.getTo() >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		edges++;
		if (!weightedEdges[e.getFrom()].contains(e)) {
			weightedEdges[e.getFrom()].add(e);
		}
		if (!directed) {
			// reverse the edge and add it to destination vertex
			WeightedEdge e2 = new WeightedEdge(e.getTo(), e.getFrom(),
					e.getWeight());
			if (!weightedEdges[e.getTo()].contains(e2)) {
				// switch the edges
				weightedEdges[e.getTo()].add(e2);
			}
			e2 = null;
		}
	}
	/**
	 * Adds a weighted edge to the graph.
	 * @param e the edge
	 * @param directed if true, the edge is directed and is only added as an 
	 * edge from the original vertext to its destination; otherwise a parallel 
	 * edge is added to the destination vertex
	 */
	public void addRoadEdge(final WeightedEdge e, final boolean directed) {
		if (e.getFrom() < 0 || e.getFrom() >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		if (e.getTo() < 0 || e.getTo() >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		edges++;
		if (!roadEdges[e.getFrom()].contains(e)) {
			roadEdges[e.getFrom()].add(e);
		}
		if (!directed) {
			// reverse the edge and add it to destination vertex
			WeightedEdge e2 = new WeightedEdge(e.getTo(), e.getFrom(),
					e.getWeight());
			if (!roadEdges[e.getTo()].contains(e2)) {
				// switch the edges
				roadEdges[e.getTo()].add(e2);
			}
			e2 = null;
		}
	}
	/**
	 * Return the list of neighbors of vertex v that can be reached by raft as 
	 * an {@link Iterable}.
	 * @param vertex the vertex being travelled from
	 * @param distance the distance travelled
	 * @return {@link Iterable}&lt;{@link Integer}&gt;
	 */
	public Iterable<Integer> getFloatingAdjacencies(final int vertex,
			final float distance) {
		if (vertex < 0 || vertex >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (distance > 0) {
			// check each edge. does it lead to a vertex whose weight is within
			// the specified distance?
			for (int i = 0; i < weightedEdges[vertex].size(); i++) {
				if (debugOn) {
					System.out.println("getFloatingAdjacencies("
							+ vertex + ", " + distance);
				}
				WeightedEdge edge = weightedEdges[vertex].get(i);
				if (debugOn) {
					System.out.println("checking edge " + edge);
				}
				float weight = edge.getWeight();
				// check for allowed moves:
				// 0.8375 - move from river to land
				// 0.375f - move upstream
				// 0.25f - move downstream
				// 0.125f - move from land to river
				if (weight == 0.8375f
						|| weight == 0.375f
						|| weight == 0.25f
						|| weight == 0.125f) {
					if (weight == 0.8375f) {
						weight = distance;				
					}
				} else {
					weight = distance + 1;
				}
				if (weight <= distance) {
					list.add(edge.getTo());
					if (debugOn) {
						System.out.println("1adding vertex "
								+ edge.getTo());
					}
					// look for more adjacencies within distance
					ArrayList<Integer> l2 =
							(ArrayList<Integer>) getFloatingAdjacencies(edge.getTo(),
									distance - weight);
					for (int inner = 0; inner < l2.size(); inner++) {
						if (l2.get(inner) != vertex) {
							if (debugOn) {
								System.out.println("2adding vertex "
										+ edge.getTo());
							}
							list.add(l2.get(inner));
						}
					}
				}
			}
		}
		return list;		
	}
	/**
	 * Gets all edges incident on a specific vertex.
	 * @param vertex the source vertex
	 * @return {@link Iterable}&lt;{@link WeightedEdge}&gt;
	 */
	public Iterable<WeightedEdge> getEdges(final int vertex) {
		if (vertex < 0 || vertex >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		return weightedEdges[vertex];
	}
	/**
	 * Gets all immediate road adjacencies to a vertex, excluding river nodes.
	 * @param vertex the source vertex
	 * @return {@link Iterable}&lt;{@link Integer}&gt;
	 */
	public Iterable<Integer> getImmediateRoadAdjacencies(final int vertex) {
		if (vertex < 0 || vertex >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < roadEdges[vertex].size(); i++) {
			list.add(roadEdges[vertex].get(i).getTo());
		}
		return list;
	}
	/**
	 * Gets all immediate adjacencies to a vertex, including hexes and river 
	 * nodes.
	 * @param vertex the source vertex
	 * @return {@link Iterable}&lt;{@link Integer}&gt;
	 */
	public Iterable<Integer> getImmediateAdjacencies(final int vertex) {
		if (vertex < 0 || vertex >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < weightedEdges[vertex].size(); i++) {
			list.add(weightedEdges[vertex].get(i).getTo());
		}
		return list;
	}
	/**
	 * Return the list of neighbors of vertex v as in Iterable.
	 * @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V
	 */
	public Iterable<Integer> getWalkingAdjacencies(final int vertex,
			final float distance) {
		if (vertex < 0 || vertex >= vertices) {
			throw new IndexOutOfBoundsException();
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (distance > 0) {
			// check each edge. does it lead to a vertex whose weight is within
			// the specified distance?
			for (int i = 0; i < weightedEdges[vertex].size(); i++) {
				if (debugOn) {
					System.out.println("getWalkingAdjacencies("
							+ vertex + ", " + distance);
				}
				WeightedEdge edge = weightedEdges[vertex].get(i);
				if (debugOn) {
					System.out.println("checking edge " + edge);
				}
				float weight = edge.getWeight();
				// check for allowed moves:
				// 1.0f - move to another land hex
				// 0.8375 - move from river to land
				// 0.125f - move from land to river
				if (weight == 1f
						|| weight == 0.8375f
						|| weight == 0.125f) {
					if (weight == 0.8375f) {
						weight = BigDecimal.valueOf(distance)
						.divideAndRemainder(BigDecimal.ONE)[1].floatValue();			
					}
				} else {
					weight = distance + 1;
				}
				if (weight <= distance) {
					list.add(edge.getTo());
					if (debugOn) {
						System.out.println("1adding vertex "
								+ edge.getTo());
					}
					// look for more adjacencies within distance
					ArrayList<Integer> l2 =
							(ArrayList<Integer>) getWalkingAdjacencies(edge.getTo(),
									distance - weight);
					for (int inner = 0; inner < l2.size(); inner++) {
						if (l2.get(inner) != vertex) {
							if (debugOn) {
								System.out.println("2adding vertex "
										+ edge.getTo());
							}
							list.add(l2.get(inner));
						}
					}
				}
			}
		}
		return list;		
	}
	/**
	 * Return the number of edges in the graph.
	 */
	public int getNumEdges() {
		return edges;
	}
	/**
	 * Return the number of vertices in the graph.
	 */
	public int getNumVertices() {
		return vertices;
	}
	public boolean removeEdge(final WeightedEdge edge) {
		boolean removed = false;
		// remove edge from first vertex
		ArrayList<WeightedEdge> list = weightedEdges[edge.getFrom()];
		removed = list.remove(edge);
		// remove from 2nd vertex
		list = weightedEdges[edge.getTo()];
		// switch the from and to for 2nd vertex
		removed = list.remove(
				new WeightedEdge(
						edge.getTo(), edge.getFrom(), edge.getWeight()));
		return removed;
	}
}
